package com.liu.algorithm.dynamicProgramming;


/**
 * 通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(n) = F(n-1) + F(n-2)
 */
public class Leetcode509 {
    public static void main(String[] args) {
        Leetcode509 obj = new Leetcode509();
        int n = 3;
        System.out.println(obj.fib(n));
    }

    public int fib(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] dpTable = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            if (i < 2) {
                dpTable[i] = i;
            } else {
                dpTable[i] = dpTable[i - 1] + dpTable[i - 2];
            }
        }
        return dpTable[n];
    }

}
